package LinkedList;//存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
//
// 返回同样按升序排列的结果链表。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,3,4,4,5]
//输出：[1,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1,1,1,2,3]
//输出：[2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围 [0, 300] 内 
// -100 <= Node.val <= 100 
// 题目数据保证链表已经按升序排列 
// 
// Related Topics 链表 双指针 👍 742 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class deleteDuplicatesII {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static ListNode deleteDuplicates(ListNode head) {

        //处理特殊情况
        if(head==null){
            return null;
        }
        // 创建虚拟头结点，且因为题目要求，虚头的值不能和其他相同
        ListNode nHead = new ListNode(-101, head);
        ListNode prev = nHead;  //当遇到一个不重复节点，prev才移动
        ListNode curStart = nHead.next; //start end 确定重复节点的开始和结束
        ListNode curEnd = nHead.next.next;
        boolean flag = false;
        /**
         * 三指针，一个头指针prev用于指向确定不重复的元素
         * curStart和end 确定重复节点的开始和结束，
         * flag用来记录当前curStart是不是也是重复元素
         * 分三种情况：
         *
         * 1.当前开始和结束指针的值相同，则end指针右移，flag=true说明当前开始指针也是重复
         * 2.开始和结束指针值不同，但flag=true表示开始指针也是重复元素，则直接跳过这些相同元素，到下一个不重复元素
         * ，即 curStart = curEnd;
         * 3.开始和结束指针不同，且开始指针不是重复，则令头指针prev指向开始指针，prev向后移
         *  开始指针指向结束指针
         *
         * */
        while(curEnd != null){
            if(curStart.val == curEnd.val){
                flag = true;
            }else if(!flag){
                prev.next = curStart;
                curStart = curEnd;
                prev = prev.next;
            }else{
                curStart = curEnd;
                flag = false;
            }
            curEnd = curEnd.next;
        }
        //当结束时，有两种情况
        if(!flag){
            prev.next = curStart;
        }else{
            prev.next = null;
        }
        return nHead.next;

    }

    static void print(ListNode head){
        while (head!=null){
            System.out.println(head.val);
            head = head.next;
        }
    }

    public static void main(String[] args) {

        ListNode head = new ListNode(1);
        head.next = new ListNode(2,new ListNode(3,
                new ListNode(3,new ListNode(4,new ListNode(4)))));
        deleteDuplicates(head);
        print(head);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
